繼第 4 天的「162. Find Peak Element」，今天來解 15 這題！還沒看過第 4 天或再之前天數的朋友，歡迎讀讀~

這題是這系列第 1 天 「1. Two Sum」 的進階題，歡迎也前往那篇讀讀。

話不多說，我們開始吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/3sum

題意

給予一個 尚未排序 的陣列 nums ，請回傳 和為 0 的所有組合，這些組合不得重複。

範例

nums = [-1, 0, 1, 2, -1, -4]

所有組合：

[[-1,-1,2],[-1,0,1]]

思維

1. 為了排除重複的值，我們必須要先將陣列排序
2. 使用三個 pointers ，以第一個 pointer 為主軸，接著從 +1 到 (count - 1) 之間，找到所有組合

2 Pointers

當要在 已排序 找到期待的 數對 的時候，就可以利用 2 pointers 技巧。

在這裡我們可以從最左和最右往中間趨近。

示意：

  f
[-4, -1, -1, 0, 1, 2]
      ^ -->    <-- ^
      left         right

程式碼

① 提早返回和排序陣列

先來建立基本的條件

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        // 當 nums 小於 3 個元素，就直接回傳空陣列
        guard nums.count >= 3 else { return [] }

        // 排序陣列
        let nums = nums.sorted(by: <)
        var results: [[Int]] = []

        // 待實作

        return results
    }
}

② 主 Pointer 走訪

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }

        let nums = nums.sorted(by: <)
        var results: [[Int]] = []
        
+        // 由於需要比較三個元素，因此只需要走訪到倒數第 3 個位置
+        for index in 0..<(nums.count-2) {
+            // 為了避免有重複結果
+            // 因此當走訪到相同值時則跳過
+            if index == 0 || nums[index] != nums[index-1] {
+                // 待實作
+            }
+        }

        return results
    }
}

④ 2 Pointers 走訪前設定初始值

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }

        let nums = nums.sorted(by: <)
        var results: [[Int]] = []

        for index in 0..<(nums.count-2) {
            if index == 0 || nums[index] != nums[index-1] {
+               let target = -nums[index]
+               // 初始在主 pointer 的右 1
+               var left = index + 1
+               // 初始在尾端
+               var right = nums.count - 1
+
+               // 待實作
            }
        }
        return results
    }
}

⑤ 找到期望值

1. 加入 results
2. 移動 2 pointers： 在移動左右指標的時候，如果遇到相同值的元素，就繼續移動直到兩指標相交

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }

        let nums = nums.sorted(by: <)
        var results: [[Int]] = []

        for index in 0..<(nums.count-2) {
            if index == 0 || nums[index] != nums[index-1] {
                let target = -nums[index]
                var left = index + 1
                var right = nums.count - 1

+                while left < right  {
+                    let sum = nums[left] + nums[right]
+                    if sum == target {
+                        results.append([nums[index], nums[left], nums[right]])
+
+                        // 跳過重複的數值
+                        while left < right && nums[left] == nums[left + 1] { left += 1 }
+                        while left < right && nums[right] == nums[right - 1] { right -= 1 }
+
+                        // 指標往中間移動
+                        left += 1
+                        right -= 1
+                    }
+                } else if sum > target {
+                    // 待實作  
+                } else {
+                   // 待實作
+                }
            }
        }
        return results
    }
}

⑤ 沒找到期望值

• 如果雙指標的和過 大 - 右指標 往 左 移
• 如果雙指標的和過 小 - 左指標 往 右 移

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }

        let nums = nums.sorted(by: <)
        var results: [[Int]] = []
        
        for index in 0..<(nums.count-2) {
            if index == 0 || nums[index] != nums[index-1] { 
                let target = -nums[index]
                var left = index + 1
                var right = nums.count - 1

                while left < right {
                    let sum = nums[left] + nums[right]
                    if sum == target {
                        results.append([nums[index], nums[left], nums[right]])

                        while left < right && nums[left] == nums[left + 1] { left += 1 }
                        while left < right && nums[right] == nums[right - 1] { right -= 1 }

                        left += 1
                        right -= 1
                    } else if sum > target {
+                        right -= 1
                    } else {
+                        left += 1
                    }
                }
            }
        }
        return results
    }
}

完整程式碼

完成後的程式碼如下：

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }

        let nums = nums.sorted(by: <)
        var results: [[Int]] = []
        
        for index in 0..<(nums.count-2) {
            if index == 0 || nums[index] != nums[index-1] { 
                let target = -nums[index]
                var left = index + 1
                var right = nums.count - 1

                while left < right {
                    let sum = nums[left] + nums[right]
                    if sum == target {
                        results.append([nums[index], nums[left], nums[right]])

                        while left < right && nums[left] == nums[left + 1] { left += 1 }
                        while left < right && nums[right] == nums[right - 1] { right -= 1 }

                        left += 1
                        right -= 1
                    } else if sum > target {
                        right -= 1
                    } else {
                        left += 1
                    }
                }
            }
        }
        return results
    }
}

執行結果

• Runtime: 155 ms (Beats 97.05%)
• Memory: 18.74 MB (Beats 33.83%)

複雜度分析

令 n 為 nums 的總數。

結語

3Sum 這題從程式碼邊看邊講解算容易，但是先用文字簡要清楚說明真的不簡單，不過還是試著寫寫看。如果有任何回饋或是文中寫不清楚的地方，歡迎在下面留言！

今天就到這裡，明天見！